package bintree.nowcoder;

/**
 * 将BST转为双向链表
 * @author yuisama
 * @date 2022/05/16 19:31
 **/
public class ConvertTree2List {
    /**
     * 传入任意一棵树的树根节点root，就能将这棵BST转为排序后的双向链表，返回链表的头结点
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        // 边界
        if(pRootOfTree == null) {
            return null;
        }
        // 1.先将左子树转为排序后的双向链表
        TreeNode leftHead = Convert(pRootOfTree.left);
        // 2.找到l1链表的尾结点和当前的树根拼接
        TreeNode leftTail = leftHead;
        while (leftTail != null && leftTail.right != null) {
            leftTail = leftTail.right;
        }
        // leftTail走到了l1的尾结点
        // 这里判空的原因左子树就是个空树
        if (leftTail != null) {
            // 进行拼接
            pRootOfTree.left = leftTail;
            leftTail.right = pRootOfTree;
        }
        // 此时l1和root连接起来了
        // 3.再将右子树也转为双向链表
        TreeNode rightHead = Convert(pRootOfTree.right);
        // 将l2的头结点和root拼接
        if (rightHead != null) {
            rightHead.left = pRootOfTree;
            pRootOfTree.right = rightHead;
        }
        // 返回链表的开始节点。
        return leftHead == null ? pRootOfTree : leftHead;
    }
}